#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 剑指 Offer 22. 链表中倒数第k个节点.py
@time: 2022/1/13 16:01
@desc: https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
'''
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution1(object):
    """
    栈
    """
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head: return None
        stack = []
        p = head
        while p:
            stack.append(p)
            p = p.next
        node = None
        for _ in range(k):
            node = stack.pop()
        return node


class Solution2(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        快慢指针
        """
        fast, slow = head, head
        for _ in range(k):
            fast = fast.next
        # fast - slow = k => slow = fast - k
        # when fast==n, slow = n-k
        while fast:
            fast = fast.next
            slow = slow.next
        return slow